package interview.numswap;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;

public class NumSwap {
	public void count() throws IOException {
		Scanner sc = new Scanner(new FileInputStream("input.txt"));
        sc.useDelimiter("\\s+");
        int[] a = new int[100000];
        int temp;
        
        long start, end;
        
        int numTestCases = sc.nextInt();
        for(int k = 0; k < numTestCases; k++) {
        	start = System.currentTimeMillis();
        	
            int numElements = sc.nextInt();
            int numSwap = 0;
            a[0] = sc.nextInt();
            int j;
            for(int i = 1; i < numElements; i++) {
            	a[i] = sc.nextInt();
                j = i;
                while(j > 0 && a[j] < a[j-1]) {
                    temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                    numSwap++;
                    j--;
                }
            }
            
            end = System.currentTimeMillis();
            
            System.out.println(numSwap);
            System.out.println(end - start);
        }
	}
	
	public void numInversions() throws FileNotFoundException {
		Scanner sc = new Scanner(new FileInputStream("input.txt"));
        sc.useDelimiter("\\s+");
        int[] a = new int[100000];
        int[] buffer = new int[100000];
              
        int numTestCases = sc.nextInt();
        for(int k = 0; k < numTestCases; k++) {
            int numElements = sc.nextInt();
            for(int i = 0; i < numElements; i++) {
            	a[i] = sc.nextInt();
            }
            
            System.out.println(numElements);
            System.out.println(mergeSortCoutingInversion(a, 0, numElements - 1, buffer));
        }
	}

	private long mergeSortCoutingInversion(int[] a, int start, int end, int[] temp) {
		if(start == end) {
			return 0;
		}
		
		int mid = start + (end - start) / 2;
		long result = mergeSortCoutingInversion(a, start, mid, temp);
		result += mergeSortCoutingInversion(a, mid + 1, end, temp);
		
		int leftIndex = start;
		int rightIndex = mid + 1;
		int tIndex = 0;
		
		while(leftIndex <= mid && rightIndex <= end) {
			if(a[leftIndex] <= a[rightIndex]) {
				temp[tIndex] = a[leftIndex];
				leftIndex++;
			} else {
				temp[tIndex] = a[rightIndex];
				rightIndex++;
				result += (mid - leftIndex + 1);
			}
			tIndex++;
		}
		
		if(leftIndex > mid) {
			while(rightIndex <= end) {
				temp[tIndex] = a[rightIndex];
				tIndex++;
				rightIndex++;
			}
			System.arraycopy(temp,0, a, start, tIndex);
			return result;
		} else {
			while(leftIndex <= mid) {
				temp[tIndex] = a[leftIndex];
				tIndex++;
				leftIndex++;
			}
			System.arraycopy(temp,0, a, start, tIndex);
			return result;
		}
	}
}
